package com.gaogzhen.introductiontoalgorithms3.foundation;

import edu.princeton.cs.algs4.MergeX;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Comparator;

/**
 * 求解逆序对的数量
 *  1 逆序：对于n个不同的元素，先规定各演示之间有一个标准次序（例如n个不同的自然数，可规定由小到大为标准次序），与是在这n个元素的任一排序中，当某一对元素的先后次序与标准次序不同时，
 *    就说它构成1个逆序。
 *  2 逆序数：一个排列中所有逆序的总数叫做这个排列的逆序数。
 * 逆序对数=交换次数
 *
 * @author gaogzhen
 * @since 2024/4/7 21:46
 */
public class Inversion {
    private static final int CUTOFF = 7;  // cutoff to insertion sort

    // This class should not be instantiated.
    private Inversion() { }

    /**
     * 归并统计交换次数
     * @param src 源子数组
     * @param dst 目的子数组
     * @param lo 起始索引
     * @param mid 中间索引
     * @param hi 结束索引
     * @return
     */
    private static int merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {

        // precondition: src[lo .. mid] and src[mid+1 .. hi] are sorted subarrays
        // assert isSorted(src, lo, mid);
        // assert isSorted(src, mid+1, hi);

        int i = lo, j = mid+1;
        // 交换次数
        int inversions = 0;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid) {
                // 低位归并完成需要计数
                dst[k] = src[j++];
            } else if (j > hi) {
                // 高位归并完成，不需要计数
                dst[k] = src[i++];
            } else if (less(src[j], src[i])) {
                // 交换次数=mid - lo + 1 - i + 1
                inversions += mid - lo + 1 - i + 1;
                dst[k] = src[j++];   // to ensure stability
            } else {
                // 归并低位需要计数
                dst[k] = src[i++];
            }
        }

        // postcondition: dst[lo .. hi] is sorted subarray
        // assert isSorted(dst, lo, hi);
        return inversions;
    }

    /**
     * 统计逆序对数
     * @param src 源子数组
     * @param dst 目的（交换）子数组
     * @param lo 低位起始索引
     * @param hi 高位终止索引
     * @return
     */
    private static int sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
        // if (hi <= lo) return;
        if (hi <= lo + CUTOFF) {
            // 小数组使用插入排序统计逆序对数
            return insertionSort(dst, lo, hi);
        }
        int mid = lo + (hi - lo) / 2;
        // 统计左子树组逆序对数
        int left = sort(dst, src, lo, mid);
        // 统计左子树组逆序对数
        int right = sort(dst, src, mid+1, hi);

        // if (!less(src[mid+1], src[mid])) {
        //    for (int i = lo; i <= hi; i++) dst[i] = src[i];
        //    return;
        // }

        // using System.arraycopy() is a bit faster than the above loop
        if (!less(src[mid+1], src[mid])) {
            // 左子树组和右子树组完成排序好，且左侧最大元素小于右侧最小元素，无需交换
            System.arraycopy(src, lo, dst, lo, hi - lo + 1);
            return left + right;
        }

        // 统计归并左右子数组逆序对数
        int inversions = merge(src, dst, lo, mid, hi);
        return inversions + left + right;
    }

    /**
     * 统计数组a的逆序对数
     * @param a 目标数组
     */
    public static int  sort(Comparable[] a) {
        Comparable[] aux = a.clone();
        int inversions =  sort(aux, a, 0, a.length-1);
        // assert isSorted(a);
        return inversions;
    }

    /**
     * 插入排序统计逆序对数
     * @param a 目标数组
     * @param lo 低位起始索引
     * @param hi 高位终止索引
     * @return
     */
    private static int insertionSort(Comparable[] a, int lo, int hi) {
        int inversions = 0;
        for (int i = lo; i <= hi; i++) {
            for (int j = i; j > lo && less(a[j], a[j-1]); j--) {
                exch(a, j, j-1);
                // 交换一次，逆序数+1
                inversions++;
            }
        }
        return inversions;
    }


    /*******************************************************************
     *  Utility methods.
     *******************************************************************/

    /**
     * 交换元素
     * @param a 目标数组
     * @param i 交换元素索引
     * @param j 另一个交换式索引
     */
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    /**
     * 第一个元素是否小于第二个元素
     * @param a 第一个元素
     * @param b 第二个元素
     * @return {@true} a 小于b ;else {@false}
     */
    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    /**
     * 使用比较器，比较a是否小于b
     * @param a 元素a
     * @param b 元素吧
     * @param comparator 比较器
     * @return
     */
    private static boolean less(Object a, Object b, Comparator comparator) {
        return comparator.compare(a, b) < 0;
    }


    /*******************************************************************
     *  Version that takes Comparator as argument.
     *******************************************************************/

    /**
     * Rearranges the array in ascending order, using the provided order.
     *
     * @param a the array to be sorted
     * @param comparator the comparator that defines the total order
     */
    public static void sort(Object[] a, Comparator comparator) {
        Object[] aux = a.clone();
        sort(aux, a, 0, a.length-1, comparator);
        // assert isSorted(a, comparator);
    }

    private static void merge(Object[] src, Object[] dst, int lo, int mid, int hi, Comparator comparator) {

        // precondition: src[lo .. mid] and src[mid+1 .. hi] are sorted subarrays
        // assert isSorted(src, lo, mid, comparator);
        // assert isSorted(src, mid+1, hi, comparator);

        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)                          dst[k] = src[j++];
            else if (j > hi)                           dst[k] = src[i++];
            else if (less(src[j], src[i], comparator)) dst[k] = src[j++];
            else                                       dst[k] = src[i++];
        }

        // postcondition: dst[lo .. hi] is sorted subarray
        // assert isSorted(dst, lo, hi, comparator);
    }


    private static void sort(Object[] src, Object[] dst, int lo, int hi, Comparator comparator) {
        // if (hi <= lo) return;
        if (hi <= lo + CUTOFF) {
            insertionSort(dst, lo, hi, comparator);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(dst, src, lo, mid, comparator);
        sort(dst, src, mid+1, hi, comparator);

        // using System.arraycopy() is a bit faster than the above loop
        if (!less(src[mid+1], src[mid], comparator)) {
            System.arraycopy(src, lo, dst, lo, hi - lo + 1);
            return;
        }

        merge(src, dst, lo, mid, hi, comparator);
    }

    // sort from a[lo] to a[hi] using insertion sort
    private static int insertionSort(Object[] a, int lo, int hi, Comparator comparator) {
        int inversions = 0;
        for (int i = lo; i <= hi; i++) {
            for (int j = i; j > lo && less(a[j], a[j-1], comparator); j--) {
                exch(a, j, j-1);
                inversions++;
            }
        }
        return inversions;
    }


    /***************************************************************************
     *  Check if array is sorted - useful for debugging.
     ***************************************************************************/
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++) {
            if (less(a[i], a[i-1])) {
                return false;
            }
        }
        return true;
    }

    private static boolean isSorted(Object[] a, Comparator comparator) {
        return isSorted(a, 0, a.length - 1, comparator);
    }

    private static boolean isSorted(Object[] a, int lo, int hi, Comparator comparator) {
        for (int i = lo + 1; i <= hi; i++) {
            if (less(a[i], a[i-1], comparator)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 输出a数组
     * @param a 数组
     */
    private static void show(Object[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        int inversions = Inversion.sort(a);
        show(a);
        StdOut.print("逆序对数：" + inversions);
    }
}
